package lc_3129_找出所有稳定的二进制数组_I;

public class Solution {
    int tot, mid, zero, one, limit;

    int mod = (int) 1e9 + 7;

    private int f(int index, int one_left, int ooo, Integer[][][] dp) {
        if (index == tot) {
            return 1;
        }
        if (dp[index][one_left][ooo] != null) {
            return dp[index][one_left][ooo];
        }
        long ans = 0;
        int zero_left = zero - (index - (one - one_left));
        if (one_left > 0 && ooo < mid + limit) {
            ans = f(index + 1, one_left - 1, ooo >= mid ? ooo + 1 : mid + 1, dp);
        }
        if (zero_left > 0 && ooo > 1) {
            ans += f(index + 1, one_left, ooo <= mid ? ooo - 1 : mid - 1, dp);

        }
        dp[index][one_left][ooo] = (int) (ans % mod);
        return dp[index][one_left][ooo];
    }

    public int numberOfStableArrays(int zero, int one, int limit) {
        tot = zero + one;
        mid = limit + 1;
        this.zero = zero;
        this.one = one;
        this.limit = limit;
        Integer[][][] dp = new Integer[tot + 1][one + 1][mid + limit + 1];
        return f(0, one, mid, dp);
    }
}